#include<iostream>
#include<vector>
#include<stack>
using namespace std;

struct TreeNode{
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : value(0), left(nullptr), right(nullptr) {}
    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
    TreeNode(int val, TreeNode* left, TreeNode* right) : value(val), left(left), right(right) {}
};

//----------------------------------------------------------------
//  二叉树的先序遍历 --- 递归版
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (!root) return vector<int>();
        vector<int> res;
        traverse(root, res);
        return res;
    }
    void traverse(TreeNode* cur, vector<int>& res) {
        if (!cur) return;
        res.push_back(cur->value); // 根
        traverse(cur->left, res);  // 左
        traverse(cur->right, res); // 右
    }
};

//  二叉树的先序遍历 --- 迭代版
class Solution {
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        if (!root) return vector<int>();
        vector<int> res;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top(); // 中
            st.pop();
            res.push_back(node->value);
            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
        }
        return res;
    }
};
// 统一的写法
class Solution {
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        if (!root) return vector<int>();
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top(); // 中
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);
                if (node->left) st.push(node->left);
                st.push(node);  // 中节点虽然访问过，但是并没有处理过
                st.push(NULL);
            } else {
                st.pop();
                node = st.top();
                st.pop();
                res.push_back(node->value);
            }
            
        }
        return res;
    }
};

//----------------------------------------------------------------
// 中序遍历---dfs
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        traverse(root, result);
        return result;
    }
    void traverse(TreeNode* root, vector<int>& out) {
        if (!root) return;
        traverse(root->left, out);
        out.push_back(root->value);
        traverse(root->right, out);
    }
};
// 


int main(int argc, char** argv) {
    return 0;
}